package com.example.system.class20;

/**
 * @Date 2022/8/16
 * @Author Jonathan
 * @Description 最长公共子序列
 */
public class Code04_LongestCommonSubSequence {
    public static void main(String[] args) {
        String str1 = "a12b3c456d";
        String str2 = "1ef23ghi4j56k";
        System.out.printf("最长公共长度是: %d\n", longestCommonSubSequence(str1, str2));
    }

    public static int longestCommonSubSequence(String str1, String str2) {
        final char[] chars1 = str1.toCharArray();
        final char[] chars2 = str2.toCharArray();
        return process(chars1, chars2, chars1.length - 1, chars2.length - 1);
    }

    // str1 = "a12b3c456d"
    // str2 = "1ef23ghi4j56k"
    public static int process(char[] chars1, char[] chars2, int i, int j) {
        // 你只有1个 我也只有1个的时候 咱们相等最长公共子序列就是1 不相等就是0
        if (i == 0 && j == 0) {
            return (chars1[i] == chars2[j]) ? 1 : 0;
        }

        if (i == 0) {
            // chars1里面只有一个的时候 只要 chars2里面有一个与之相等 就是1
            // 我只有一个元素 你有很多元素的话  你只要有一个和我相等 那公共长度就是1
            for (int k = 0; k <= j; k++) {
                if (chars1[i] == chars2[k]) {
                    return 1;
                }
            }
            return 0;
        }

        if (j == 0) {
            // 我有很多元素 你只有一个元素 我只有有一个和你相等  最长子序列就是1
            for (int k = 0; k <= i; k++) {
                if (chars1[k] == chars2[j]) {
                    return 1;
                }
            }
            return 0;
        }
        // 任意的情况
        if (chars1[i] == chars2[j]) {
            return process(chars1, chars2, i - 1, j - 1) + 1;
        } else {
            return Math.max(process(chars1, chars2, i - 1, j), process(chars1, chars2, i, j - 1));
        }
    }
}
